package leetcode.list;

import java.util.HashSet;

/**
 * Created by zxc on 2018/10/3.
 * 链表中可能存在环，若有环返回环起始节点
 */
public class DetectListCycle {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }

    /*链表中可能存在环，若有环返回环起始节点， 使用HashSet来做 ,另一种方法，快慢指针法此处不做*/
    private static ListNode detectListCycleA(ListNode headA) {
        ListNode retNode = null;
        HashSet<ListNode> lst = new HashSet<>();
        while (headA != null){
            if(lst.contains(headA)){
                retNode = headA;
                break;
            }
            lst.add(headA);
            headA = headA.next;
        }
        return retNode;
    }

    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node7 = new ListNode(7);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;
        node6.next=node7;
        node7.next=node3;
        ListNode  headA = node1;

        System.out.println("Before find:");
        System.out.print("headA:");
        int i=7;
        while (headA!=null && (i--)!=0){
            System.out.print(headA.val+">");
            headA = headA.next;
        }
        System.out.println("end");

        /*链表中可能存在环，若有环返回环起始节点*/
        ListNode newHead = detectListCycleA (node1);

        if(newHead != null) {
            System.out.println("find环起始点：" + newHead.val);
        }else{
            System.out.println("无环起始点" );
        }

        System.out.println("end");
    }
}
